/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

// 执行用时：1412 ms, 在所有 C 提交中击败了5.11% 的用户
// 内存消耗：170.1 MB, 在所有 C 提交中击败了6.57% 的用户
void find_max_min(int arr[], int n, int *max, int *min) {
    int min_idx = 0, max_idx = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] < arr[min_idx]) min_idx = i;
        if (arr[i] > arr[max_idx]) max_idx = i;
    }
    *max = arr[max_idx];
    *min = arr[min_idx];
}

typedef struct tree_node {
    int start;
    int end;
    int count;  // 落在[start, end]区间的元素个数
    struct tree_node *left;
    struct tree_node *right;
} node_t;

// 创建一个新的空节点
node_t *make_newnode(int start, int end) {
    node_t *node = malloc(sizeof(*node));
    node->start = start;
    node->end = end;
    node->count = 0;
    node->left = NULL;
    node->right = NULL;
    return node;
}

node_t *build_seg_tree(int start, int end) {
    node_t *root = make_newnode(start, end);
    if (start == end) {
        //root->count = 0;
    } else {    // 递归创建节点
        // int mid = (start + end) / 2; // 如果是负数会有问题，，，
        int mid = start + (end - start)/2;
        root->left  = build_seg_tree(start, mid);
        root->right = build_seg_tree(mid + 1, end); 
    }
    return root;
}

// 添加一个元素到线段树，元素所属的区间，都加1  //元素添加与线段树节点个数无关，线段树只负责记录元素个数
void insert_val(node_t *tree, int val) {
    if (val >= tree->start && val <= tree->end) {
        tree->count++;
        if (tree->left)
            insert_val(tree->left, val);
        if (tree->right)
            insert_val(tree->right, val);
    }
}

void delete_val(node_t *tree, int val) {
    if (val >= tree->start && val <= tree->end) {
        tree->count--;
        if (tree->left)
            delete_val(tree->left, val);
        if (tree->right)
            delete_val(tree->right, val);
    }
}


// 查询落在[L, R]区间中的元素的个数
int query_count(node_t *tree, int L, int R) {
    if (tree == NULL || L > R) return 0;    // 递归出口
    if (L > tree->end || R < tree->start)   // 没有落在区间
        return 0;
    else if (tree->start == tree->end || L <= tree->start && tree->end <= R)    // 包含的区间
        return tree->count;
    else {
        int left_count = query_count(tree->left, L, R);
        int right_count = query_count(tree->right, L, R);
        return (left_count + right_count);
    }
}

int* countSmaller(int* nums, int numsSize, int* returnSize){
    int min, max;
    find_max_min(nums, numsSize, &max, &min);
    // printf("min:%d max:%d\n", min, max);

    node_t *tree = build_seg_tree(min, max);
    for (int i = 0; i < numsSize; i++) {
        insert_val(tree, nums[i]);
    }
    // for (int i = 0; i < numsSize; i++) 
    //     printf("落在区间[%d, %d]的元素个数：%d\n", min, nums[i], query_count(tree, min, nums[i]));
    // printf("\n");

    int *res = calloc(numsSize, sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        res[i] = query_count(tree, min, nums[i]-1);   //查询落在[min, nums[i])区间的元素个数
        delete_val(tree, nums[i]);  //nums[i]已经用过，不能再考虑
    }

    *returnSize = numsSize;
    return res; 
}